package sort;

import java.util.Arrays;

public class QuickSort1 {
    public static void main(String[] args) {
        int[] ints = {9, 2, 1, 8, 7, 5, 3, 4, 6};
        quick(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints));
    }

    public static void quick(int[] arr, int begin, int end) {
        int left = begin;
        int right = end;

        if (left > right) {
            return;
        }
        int pivot = arr[left];
        while (left != right) {
            while (arr[right] >= pivot && left < right) {
                right--;
            }
//            arr[left] = arr[right];
            while (arr[left] <= pivot && left < right) {
                left++;
            }
//            int temp = arr[left];
//            arr[right] = arr[left];

            if(left < right) {
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;

            }
        }
//        arr[left] = pivot;

        int p = arr[left];
        arr[left] = arr[begin];
        arr[begin] = p;

        quick(arr, begin, left - 1);
        quick(arr, left + 1, end);


    }
}


